1. Field of the Invention
The present invention relates generally to coordination amongst execution sequences in a multiprocessor computer, and more particularly, to structures techniques for facilitating non blocking implementations of shared data structures.
2. Description of the Related Art
Significant research effort has been applied in recent years to the development nonblocking implementations of shared data structures. Typically, this work is aimed at avoiding the numerous problems associated with the use of mutually exclusive locks when accessing shared data structures. These problems include deadlock, convoying and priority inversion and are generally well known in the art.
By using locks, operations on a shared data structure can prevent concurrent operations from accessing (parts of) the data structure for certain periods of time. In contrast, an operation in a nonblocking implementation of a shared data structure can be interrupted at any moment by another operation, and therefore the implementation must typically keep data consistent in every state, rather than simply ensuring that the data are consistent before releasing a lock. This presents a challenge, because if we want to change multiple parts of the data structure then we must prevent another operation from “seeing” some parts of the updates but not others.
Because current hardware architectures do not typically support an atomic modification of multiple, non-contiguous memory locations, it would be desirable to provide the illusion of this atomicity in software. Unfortunately, achieving this goal has proven difficult, particularly when we consider that nonoverlapping sets of atomic updates should not interfere with each other's performance if there is to be any hope of scalability of applications and data structure implementations that would employ the atomic updates. There has been a considerable amount of research directed toward providing abstractions to-relieve designers of the burden of the difficult reasoning that is needed in these cases.
One approach, originally proposed by Herlihy, envisions universal constructions that automatically produce nonblocking implementations of shared data structures given only sequential code for their operations. See M. Herlihy, A Methodology for Implementing Highly Concurrent Data Objects, ACM Transactions on Programming Languages and Systems, 15(5):745-770 (1993). This approach is attractive because it completely relieves designers of the burden of reasoning about concurrency. Unfortunately, Herlihy's original constructions are expensive in time and in space, and do not exploit parallelism between concurrent operations even if they do not access overlapping parts of the data structure. However, there has been a fair amount of work since on universal constructions, which addresses some or all of those problems. See e.g., J. Anderson and M. Moir, Universal Constructions for Large Objects, IEEE Transactions on Parallel and Distributed Systems, 10(12):1317-1332 (1999); M. Moir, Transparent Support for Wait-free Transactions, In Proceedings of the 11th International Workshop on Distributed Algorithms, pp. 305-319 (1997); M. Moir, Laziness pays! Using Lazy Synchronization Mechanisms to Improve Non-Blocking Constructions, In Proceedings of the 19th Annual ACM Symposium on the Principles of Distributed Computing, pp. 61-70 (2000). Unfortunately, despite significant progress, these approaches are still not widely used in practice, partly because the generality of the approaches tends to preclude optimizations that are based on knowledge of the semantics of a particular data structure being implemented.
Another approach that does not present this same set of practical limitations is to provide programmers with stronger support for implementing nonblocking shared data structures, without attempting to completely relieve them of the burden of reasoning about concurrency. Such approaches can significantly ease the task of designing and reasoning such data structures, while still leaving room for optimizations based on semantics of the data structure being implemented. An important feature of such mechanisms is support for the illusion that we can read and modify multiple memory locations atomically, as this substantially simplifies reasoning about invariants on the data.
Several interfaces can be considered for providing such an illusion; in general the key synchronization mechanisms used to support these interfaces are not very different, but ease of use for programmers and efficiency of implementations can differ greatly. One class of such interfaces is transactional memory, in which programmers can designate certain sequences of operations as “transactions,” which are guaranteed by the transactional memory implementation to either take effect atomically and in their entirety (in which case we say they succeed), or have no externally visible effect (in which case we say that they fail). Several variations on the programmer interface to transactional memory have been considered in the past, and both hardware and software solutions have been proposed. See e.g., M. Herlihy and J. Moss, Transactional Memory: Architectural Support for Lock-Free Data Structures, In Proceedings of the 20th International Symposium in Computer Architecture, pp. 289-300 (1993); N. Shavit and D. Touitou, Software Transactional Memory, Distributed Computing, Special Issue (10):99-116 (1997).
Unfortunately, prior designs for software transactional memory have required that both memory usage and the set of transactions that access transactional memory be defined statically in advance. Techniques are desired whereby these and other restrictions can be relaxed.